package com.likou;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class q145 {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode p = root;
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode pop = null;
        while (p != null || !deque.isEmpty()) {
            while (p != null) {
                deque.push(p);
                p = p.left;
            }

            TreeNode peek = deque.peek();
            if (peek.right == null) {
                list.add(peek.val);
                pop = deque.pop();
            } else if (peek.right == pop) {
                list.add(peek.val);
                pop = deque.pop();
            } else {
                p = peek.right;
            }
        }

        return list;
    }

//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        TreeNode p = root;
//        postorder(p, list);
//
//        return list;
//    }
//
//    private void postorder(TreeNode p, List<Integer> list) {
//        if (p == null) {
//            return;
//        }
//        postorder(p.left, list);
//        postorder(p.right, list);
//        list.add(p.val);
//    }

}
